package com.sali.BFS;

import java.util.*;

/**
 * 给定编号从 0 到 n - 1 的 n 个  结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。
 * <p>
 * 如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。
 */
public class LeetCode_261 {


    public boolean validTree(int n, int[][] edges) {
        if (edges.length + 1 != n) {
            return false;
        }

        List<Integer>[] adj = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        Queue<Integer> myQue = new ArrayDeque<>();
        HashSet<Integer> visited = new HashSet<>();


        myQue.offer(0);
        visited.add(0);

        while (!myQue.isEmpty()) {
            int size = myQue.size();
            for (int i = 0; i < size; i++) {
                int node = myQue.poll();
                List<Integer> nextNodeList = adj[node];
                for (int j = 0; j < nextNodeList.size(); j++) {
                    Integer nextNode = nextNodeList.get(j);
                    if (!visited.contains(nextNode)) {
                        myQue.offer(nextNode);
                        visited.add(nextNode);
                    }
                }
            }
        }

        return n == visited.size();

    }

}
